package LeetCode;

public class LC_075_SortColors {
    public static void main(String[] args) {

    }

    static class Solution {
        public void sortColors(int[] nums) {
            if (nums == null)
                return;

            int count = 0;
            int sum = 0;

            for (int i : nums) {
                if (i == 1)
                    count++;
                sum += i;
            }

            sum = (sum - count) / 2;
            count = nums.length - count - sum;
            sum = nums.length - sum;

            for (int i = 0; i < count; i++)
                nums[i] = 0;

            for (int i = count; i < sum; i++)
                nums[i] = 1;

            for (int i = sum; i < nums.length; i++)
                nums[i] = 2;
        }
    }

    static class Solution_2 {
        public void sortColors(int[] nums) {
            if (nums == null || nums.length < 2)
                return;

            int[] countArray = new int[3];
            for (int num : nums)
                countArray[num]++;

            for (int i = 1; i <= 2; i++)
                countArray[i] = countArray[i - 1] + countArray[i];

            int[] sorted = new int[nums.length];
            for (int num : nums) {
                int index = countArray[num] - 1;
                countArray[num] = countArray[num] - 1;
                sorted[index] = num;
            }

            System.arraycopy(sorted, 0, nums, 0, nums.length);
        }
    }
}
